package zuoshen.class02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Code06_QuickSort {

	/*public static void quickSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		quickSort(arr, 0, arr.length - 1);
	}

	public static void quickSort(int[] arr, int l, int r) {
		if (l < r) {
			swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
			int[] p = partition(arr, l, r);
			quickSort(arr, l, p[0] - 1);
			quickSort(arr, p[1] + 1, r);
		}
	}

	//r位置上的数不变
	public static int[] partition(int[] arr, int l, int r) {
		int less = l - 1;
		int more = r;
		while (l < more) {
			if (arr[l] < arr[r]) {
				swap(arr, ++less, l++);
			} else if (arr[l] > arr[r]) {
				swap(arr, --more, l);
			} else {
				l++;
			}
		}
		swap(arr, more, r);
		return new int[] { less + 1, more };
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}*/

	public static void quickSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		quickSort(arr, 0, arr.length - 1);
	}

	public static void quickSort(int[] arr,int low,int high){
		int i,j,temp,t;
		if(low>high){
			return;
		}
		i=low;
		j=high;
		//temp就是基准位
		temp = arr[low];

		while (i<j) {
			//先看右边，依次往左递减
			while (temp<=arr[j]&&i<j) {
				j--;
			}
			//再看左边，依次往右递增
			while (temp>=arr[i]&&i<j) {
				i++;
			}
			//如果满足条件则交换
			if (i<j) {
				t = arr[j];
				arr[j] = arr[i];
				arr[i] = t;
			}

		}
		//最后将基准为与i和j相等位置的数字交换
		arr[low] = arr[i];
		arr[i] = temp;


		//递归调用左半数组
		quickSort(arr, low, i-1);
		//递归调用右半数组
		quickSort(arr, i+1, high);
	}



	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

	// for test
	public static void comparator(int[] arr) {
		Arrays.sort(arr);
	}

	// for test
	public static int[] generateRandomArray(int maxSize, int maxValue) {
		int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
		}
		return arr;
	}

	// for test
	public static int[] copyArray(int[] arr) {
		if (arr == null) {
			return null;
		}
		int[] res = new int[arr.length];
		for (int i = 0; i < arr.length; i++) {
			res[i] = arr[i];
		}
		return res;
	}

	// for test
	public static boolean isEqual(int[] arr1, int[] arr2) {
		if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
			return false;
		}
		if (arr1 == null && arr2 == null) {
			return true;
		}
		if (arr1.length != arr2.length) {
			return false;
		}
		for (int i = 0; i < arr1.length; i++) {
			if (arr1[i] != arr2[i]) {
				return false;
			}
		}
		return true;
	}

	// for test
	public static void printArray(int[] arr) {
		if (arr == null) {
			return;
		}
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	/*public static void main(String[] args) {
		int testTime = 1000;
		int maxSize = 100;
		int maxValue = 100;
		boolean succeed = true;
		for (int i = 0; i < testTime; i++) {
			int[] arr1 = generateRandomArray(maxSize, maxValue);
			int[] arr2 = copyArray(arr1);
			quickSort(arr1);
			comparator(arr2);
			if (!isEqual(arr1, arr2)) {
				succeed = false;
				printArray(arr1);
				printArray(arr2);
				break;
			}
		}
		int[] arr1 = generateRandomArray(maxSize, maxValue);
		quickSort(arr1);
		System.out.println(succeed ? "Nice!" : "Fucking fucked!");


	}*/

	public static List<List<Integer>> fourSum(int[] nums, int target) {
		if(nums.length == 0){
			return new ArrayList<>();
		}
		Arrays.sort(nums);
		List<List<Integer>> res = new ArrayList<>();
		int len = nums.length;
		int temp = 0;
		int cur = 0;
		for(int i = 0; i < len - 2; i ++){
			if(i > 0 && nums[i] == nums[i - 1])continue;
			for(int j = i + 1 ; j <len - 2; j ++){
				if(j > i + 1 && nums[j] == nums[j - 1])continue;
				int left = j + 1;
				int right = len - 1;
				temp = target - nums[i];
				while(left < right){
					cur = nums[j] + nums[left] + nums[right];
					if(cur < temp){
						while(left < right){
							left++;
							if(nums[left] != nums[left - 1]){
								break;
							}
						}
					}else if(cur > temp){
						while(left < right){
							right--;
							if(nums[right] != nums[right + 1]){
								break;
							}
						}
					}else{
						List<Integer> list = new ArrayList<>();
						list.add(nums[i]);
						list.add(nums[j]);
						list.add(nums[left]);
						list.add(nums[right]);
						res.add(list);
						while(left < right){
							left++;
							if(nums[left] != nums[left - 1]){
								break;
							}
						}
					}
				}
			}
		}
		return res;
	}

	public static void main(String[] args) {
//		boolean[] arr = new boolean[2];
//		System.out.println(arr[0]);

		int[] arr = new int[]{-2,-1,-1,1,1,2,2};
		fourSum(arr,0);

	}

}
